package com.lwt.codetop.linkedLists;

import java.util.HashMap;
import java.util.Map;

/**
 * 146. LRU Cache
 */

// 定义一个双向链表Node，用于实现缓存的LRUCache机制
class Node {
    int key;
    int value;
    Node left;
    Node right;
    public Node() {}
    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}


public class LRUCache {

    private int capacity;
    private Node L, R;
    private Map<Integer, Node> h = new HashMap<>();

    // 构造函数,初始化
    public LRUCache(int capacity) {
        this.capacity = capacity;
        // 初始化双链表 头尾节点L R
        L = new Node(0, 0);
        R = new Node(0, 0);
        L.right = R;
        R.left = L;
    }

    /**
     * 从缓存中获取元素：remove insert：删除旧节点，将其移动/插入到链表头部（表示最新访问）
     * @param key
     * @return
     */
    public int get(int key){
        Node p = h.get(key);
        if (p == null) {
            return -1;
        }
        // remove
        removeNode(p);

        //  insert
        insertTohead(p);

        return  p.value;
    }

    /**
     * 向缓存中插入元素：
     *      若元素存在，则覆盖 然后 remove insert
     *      若元素不存在: 判断缓存是否满了
     *          满了, 进行LRUCache更新，即获取链表尾节点，然后删除，同时删除缓存中的元素
     *          不管满了还是未满，最后都要进行新建元素然后插入 insert
     *
     * @param key
     * @param value
     */
    public void put(int key, int value) {
        Node p = h.get(key);
        if (p != null){ // 存在 则覆盖
            p.value = value;
            removeNode(p);
            insertTohead(p);
        }else {// 不存在
            if(h.size() ==  capacity) { // 满了
                Node tail = R.left;
                removeNode(tail);
                h.remove(tail.key);
            }
            Node newNode = new Node(key, value);
            h.put(key, newNode);
            insertTohead(newNode);
        }
    }

    /**
     * 更新元素：将最新访问的元素移动到链表头部
     * @param p
     */
    private void insertTohead(Node p) {
        p.right = L.right;
        p.left = L;
        L.right.left = p;
        L.right = p;
    }

    /**
     * 删除元素：删除双链表的节点
     * @param p
     */
    private void removeNode(Node p) {
        p.left.right = p.right;
        p.right.left = p.left;
    }


    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);
        System.out.println("Get key 1: " + cache.get(1));
        cache.put(3, 3);
        System.out.println("Get key 2: " + cache.get(2));
    }
}
